package org.example.y24.m11;
import java.util.*;

public class MazeSolver {
    private static final int MAX_SIZE = 50;
    private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final int EMPTY = 0; // 空地
    private static final int OBSTACLE = 1; // 障碍物
    private static final int VISITED = 2; // 已访问

    public static void main(String[] args) {
        int n = 5, m = 5; // 迷宫大小
        int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
        };
        int startX = 0, startY = 0; // 起点
        int endX = 4, endY = 2; // 终点

        int shortestPathLength = solveMaze(maze, n, m, startX, startY, endX, endY);
        if (shortestPathLength != -1) {
            System.out.println("最短路径长度: " + shortestPathLength);
        } else {
            System.out.println("no way.");
        }
    }

    private static int solveMaze(int[][] maze, int n, int m, int startX, int startY, int endX, int endY) {
        return bfs(maze, n, m, startX, startY, endX, endY);
    }

    private static int bfs(int[][] maze, int n, int m, int startX, int startY, int endX, int endY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY, 0});
        maze[startX][startY] = VISITED;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], pathLength = current[2];
            printMaze(maze, n, m);
            if (x == endX && y == endY) {
                return pathLength; // 找到了路径
            }

            for (int[] dir : directions) {
                int newX = x + dir[0], newY = y + dir[1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] == EMPTY) {
                    queue.offer(new int[]{newX, newY, pathLength + 1});
                    maze[newX][newY] = VISITED; // 标记为已访问
                }
            }
        }
        return -1; // 没有找到路径
    }

    private static void printMaze(int[][] maze, int n, int m) {
        System.out.println("Current maze state:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("---------------------");
    }
}
